package leetbook.link;

import datastruct.list.ListNode;

public class Solution328 {

    /**
     * 拆分成奇偶链表最后合并
     * @param head
     * @return
     */
    public ListNode oddEvenList(ListNode head) {
        ListNode oddHead = new ListNode(), oddTail = oddHead;
        ListNode evenHead = new ListNode(), evenTail = evenHead;
        int count = 1;
        while (head!=null){
            //暂存原链表的下一个节点
            ListNode next = head.next;
            if((count&1)==1) {
                //把原链表的当前节点放到新链表末尾
                head.next = oddTail.next;
                oddTail.next = head;
                //新链表末尾更新
                oddTail = oddTail.next;
            }else {
                //把原链表的当前节点放到新链表末尾
                head.next = evenTail.next;
                evenTail.next = head;
                //新链表末尾更新
                evenTail = evenTail.next;
            }
            head = next;
            count++;
        }
        //拼接
        oddTail.next = evenHead.next;

        return oddHead.next;
    }
}
